package dp.子序列;

/**
 * @author songZiHao
 * @version 1.0.0
 * @ClassName N判断子序列392.java
 * @Description https://leetcode-cn.com/problems/is-subsequence/
 * @createTime 2021年11月22日 21:02:00
 *
 * 给定字符串 s 和 t ，判断 s 是否为 t 的子序列。
 *
 * 字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）
 *
 */
public class N判断子序列392 {
	public boolean isSubsequence(String s, String t) {
		int n = s.length(), m = t.length();
		/**
		 * dp[i][j]表示 字符串t中从 位置i开始往后字符 j 第一次出现的位置
		 *
		 */
		int[][] f = new int[m + 1][26];

		/**
		 * 初始化状态
		 * 	f[m][..] 为 mm
		 */
		for (int i = 0; i < 26; i++) {
			f[m][i] = m;
		}
		/**
		 * 状态方程：
		 *  	如果位置i的字符就是j。那么dp[i][j]=i
		 *  	否则 jj 出现在位置 i+1i+1 开始往后，即 f[i][j]=f[i+1][j]f[i][j]=f[i+1][j]
		 *
		 */
		for (int i = m - 1; i >= 0; i--) {
			for (int j = 0; j < 26; j++) {
				if (t.charAt(i) == j + 'a') {
					f[i][j] = i;
				} else {
					f[i][j] = f[i + 1][j];
				}
			}
		}

		int add = 0;
		for (int i = 0; i < n; i++) {
			if (f[add][s.charAt(i) - 'a'] == m) {
				return false;
			}
			add = f[add][s.charAt(i) - 'a'] + 1;
		}
		return true;
	}
}
